/*
Abstract:
  Analyze by fragments functionality implementation

Last changed:
  $Id: analyze_fragments.cpp 88 2010-01-15 01:06:37Z vitamin.caig $

Author:
  (C) Vitamin/CAIG/2001

  This file is the part of Textator project
*/

#include "analyzer.h"
#include "../io/logging.h"

#include <set>
#include <stack>
#include <limits>
#include <cassert>
#include <numeric>
#include <algorithm>

#include <text.h>

namespace
{
  typedef unsigned PenaltyType;
  const PenaltyType MAX_PENALTY = std::numeric_limits<PenaltyType>::max();

  struct Fragment
  {
    Fragment(String::size_type beg, String::size_type size, struct FragValue* hive)
      : Begin(beg), Size(size), FragHive(hive)
    {
    }
    String::size_type Begin;
    String::size_type Size;
    struct FragValue* const FragHive;

    bool operator < (const Fragment& rh) const
    {
      return Begin < rh.Begin ? true : (Begin == rh.Begin ? Size < rh.Size : false);
    }
  };

  //list because FragRefSet should contain stable references to Fragment element
  typedef std::list<Fragment> FragmentsSet;

  inline FragmentsSet::iterator AddFragment(FragmentsSet& fs, const Fragment& frag)
  {
    fs.push_back(frag);
    FragmentsSet::iterator res(fs.end());
    return --res;
  }

  inline bool IsOverlapped(const Fragment& lh, const Fragment& rh)
  {
    assert(lh.Begin <= rh.Begin);
    return lh.Begin + lh.Size > rh.Begin;
  }

  class FragmentsHolder
  {
  public:
    FragmentsHolder(FragmentsSet* cont, FragmentsSet::iterator it) : Container(cont), Iterator(it)
    {
    }

    const FragmentsHolder& operator = (const FragmentsHolder& rh)
    {
      Container = rh.Container;
      Iterator = rh.Iterator;
      return *this;
    }

    void Remove()
    {
      assert(Container && Container->end() != Iterator);
      Container->erase(Iterator);
      Iterator = Container->end();
    }
  private:
    FragmentsSet* Container;
    FragmentsSet::iterator Iterator;
  };

  typedef std::vector<FragmentsHolder> FragRefsSet;

  template<class T>
  inline T sqr(T val)
  {
    return val * val;
  }

  template<class T, class S>
  inline T SafeSub(S lh, S rh)
  {
    const T limit = std::numeric_limits<T>::max();
    return (lh < static_cast<S>(limit)) ? static_cast<T>(lh) - rh : limit;
  }

  struct FragValue
  {
    explicit FragValue(const String& value) : References(), Value(value), Penalty(0), Cost(0), Neighbours(), Weight()
    {
    }

    void RemoveAll()
    {
      std::for_each(References.begin(), References.end(), std::mem_fun_ref(&FragmentsHolder::Remove));
    }

    std::size_t RefCount() const
    {
      return References.size();
    }

    void Reset()
    {
      Penalty = 0;
      Cost = sqr(RefCount() * Value.size());
      Neighbours.clear();
    }
    
    void CalcWeight()
    {
      Weight = SafeSub<long>(Penalty, Cost);
    }

    bool Unlink()
    {
      bool result = Penalty != MAX_PENALTY;
      for (std::vector<FragValue*>::iterator it = Neighbours.begin(), lim = Neighbours.end(); result && it != lim; ++it)
      {
        assert(*it);
        result = (*it)->Penalty != MAX_PENALTY;
      }
      if (result)
      {
        for (std::vector<FragValue*>::iterator it = Neighbours.begin(), lim = Neighbours.end(); it != lim; ++it)
        {
          FragValue* const val = *it;
          val->Penalty -= Cost;
          val->Weight -= Cost;
          const std::vector<FragValue*>::iterator end = 
            std::remove(val->Neighbours.begin(), val->Neighbours.end(), this);
          val->Neighbours.resize(std::distance(val->Neighbours.begin(), end));
        }
      }
      return result;
    }

    FragRefsSet References;
    const String Value;
    PenaltyType Penalty;
    unsigned Cost;
    std::vector<FragValue*> Neighbours;
    long Weight;
  };

  //list is because Fragment should have stable reference to FragValue element
  typedef std::list<FragValue> FragValsSet;

  inline FragValsSet::iterator AddFragValue(FragValsSet& fvs, const String& value)
  {
    fvs.push_back(FragValue(value));
    FragValsSet::iterator res(fvs.end());
    return --res;
  }

  struct PreTokenizedEntry
  {
    explicit PreTokenizedEntry(const String& val) : Value(val)
    {
    }
    String Value;
    FragmentsSet Fragments;
  };
  typedef std::map<String, PreTokenizedEntry> PreTokenizedMap;

  typedef StringMap TokensMap;

  inline std::size_t CalcStrLen(std::size_t inVal, const StringMap::value_type& str)
  {
    return inVal + str.second.size();
  }

  inline bool IsRepeatable(const String& str)
  {
    assert(str.size() >= 2);//minimal size for check
    for (String::const_iterator it1 = str.begin(), lim = str.end(); ++it1 != lim; )
    {
      if (std::equal(it1, lim, str.begin()))
      {
        return true;
      }
    }
    return false;
  }

  void ExtractFragments(const StringMap& src, const Analyzer::ByFragmentsParameters& params,
    PreTokenizedMap& ptm, FragValsSet& fragRefs)
  {
    Log::Message(TEXT_MESSAGE_SEARCHING_FRAGMENTS);
    fragRefs.clear();
    ptm.clear();
    typedef std::map<String, FragValsSet::iterator> Frag2Val;
    Frag2Val fragsSet;
    //progress support
    const std::size_t totalLen = std::accumulate(src.begin(), src.end(), 0, CalcStrLen);
    std::size_t curLen(0);
    for (StringMap::const_iterator it = src.begin(), lim = src.end(); it != lim; curLen = CalcStrLen(curLen, *it), ++it)
    {
      PreTokenizedMap::iterator eiter(ptm.insert(PreTokenizedMap::value_type(it->first, PreTokenizedEntry(it->second))).first);
      const String& val(eiter->second.Value);
      if (val.size() < params.MinFragmentSize)//not tokenizeable
      {
        continue;
      }
      FragmentsSet& fragments(eiter->second.Fragments);
      const String::size_type vallim(val.size());
      for (String::size_type frBeg = 0; frBeg != vallim - params.MinFragmentSize; ++frBeg)
      {
        for (String::size_type len = params.MinFragmentSize;
          len <= params.MaxFragmentSize && frBeg + len <= vallim;
          ++len)
        {
          const String& frgTxt(val.substr(frBeg, len));

          //test for self-overlapping
          if (frBeg && IsRepeatable(frgTxt))
          {
            String::size_type lastOk(val.find(frgTxt));
            for (String::size_type mpos = val.find(frgTxt, lastOk + 1); 
              String::npos != mpos && mpos < frBeg; mpos = val.find(frgTxt, mpos + 1))
            {
              if (lastOk + frgTxt.size() <= mpos)
              {
                lastOk = mpos;
              }
            }
            if (lastOk != frBeg &&
                lastOk + frgTxt.size() > frBeg)
            {
              Log::Debug("Not usable fragment '$1'", frgTxt);
              continue;//not usable fragment
            }
          }

          FragValsSet::iterator curFragVal;
          Frag2Val::iterator fr2vit(fragsSet.find(frgTxt));
          if (fragsSet.end() == fr2vit)
          {
            //new fragment
            curFragVal = AddFragValue(fragRefs, frgTxt);
            fragsSet.insert(Frag2Val::value_type(frgTxt, curFragVal));
          }
          else
          {
            curFragVal = fr2vit->second;
          }

          FragmentsSet::iterator curFrag(AddFragment(fragments, Fragment(frBeg, len, &*curFragVal)));
          curFragVal->References.push_back(FragmentsHolder(&eiter->second.Fragments, curFrag));
        }
        Log::ProgressMessage(curLen + frBeg, totalLen);
      }
    }
    Log::ProgressMessage(totalLen, totalLen);
  }

  template<class T>
  inline bool SafeAdd(T& lh, T rh)
  {
    const T result = lh + rh;
    if (result > lh)
    {
      lh = result;
      return true;
    }
    lh = std::numeric_limits<T>::max();
    return false;
  }

  inline void EvaluatePreTokenizedEntry(PreTokenizedMap::value_type& val)
  {
    FragmentsSet& fragments(val.second.Fragments);
    for (FragmentsSet::iterator fit = fragments.begin(), flim = fragments.end(); fit != flim; ++fit)
    {
      FragmentsSet::iterator nit(fit);
      while (++nit != flim && IsOverlapped(*fit, *nit))
      {
        FragValue* const first(fit->FragHive);
        FragValue* const second(nit->FragHive);
        if (SafeAdd(first->Penalty, second->Cost))
        {
          first->Neighbours.push_back(second);
        }
        if (SafeAdd(second->Penalty, first->Cost))
        {
          second->Neighbours.push_back(first);
        }
      }
    }
  }
  
  inline bool CompareByWeight(const FragValsSet::value_type& lh, const FragValsSet::value_type& rh)
  {
    return lh.Weight < rh.Weight;
  }

  class FragmentAnalyzer
  {
  public:
    FragmentAnalyzer() : MaxValue(std::numeric_limits<long>::max()), LastValue(0)
    {
      Log::Message(TEXT_MESSAGE_ANALYZE_FRAGMENTS);
    }

    ~FragmentAnalyzer()
    {
      Log::ProgressMessage(MaxValue, MaxValue);
    }

    bool RemoveBadFragment(FragValsSet& vals)
    {
      bool running = true;
      while (running)
      {
        FragValsSet::iterator it(std::max_element(vals.begin(), vals.end(), CompareByWeight));
        if (it == vals.end() || it->Weight <= 0)
        {
          return false;
        }
        const long curValue(it->Weight);
        Log::Debug("Removing fragment '$1', c/p: $2/$3 val: $4", it->Value, it->Cost, it->Penalty, curValue);
        running = it->Unlink();
        it->RemoveAll();
        vals.erase(it);

        if (curValue != LastValue)
        {
          LastValue = curValue;
          if (MaxValue == std::numeric_limits<long>::max())
          {
            MaxValue = curValue;
          }
          else
          {
            Log::ProgressMessage(MaxValue - LastValue, MaxValue);
          }
        }
      }
      return true;
    }

  private:
    long MaxValue;
    long LastValue;
  };

  inline void RemoveTokens(FragValsSet& frags, std::size_t limit)
  {
    std::stack<FragValsSet::iterator> toDelete;
    for (FragValsSet::iterator it = frags.begin(), lim = frags.end(); it != lim; ++it)
    {
      if (it->RefCount() < limit)
      {
        toDelete.push(it);
      }
    }
    while (!toDelete.empty())
    {
      toDelete.top()->RemoveAll();
      frags.erase(toDelete.top());
      toDelete.pop();
    }
  }

  void OptimizeFragments(const Analyzer::ByFragmentsParameters& params,
    PreTokenizedMap& ptm, FragValsSet& fragRefs)
  {
    FragmentAnalyzer anlzer;
    //remove fragments with not enough references
    RemoveTokens(fragRefs, params.MinFragmentReferences);
    for (;;)
    {
      //reset value/penalty
      std::for_each(fragRefs.begin(), fragRefs.end(), std::mem_fun_ref(&FragValue::Reset));
      //evaluate
      std::for_each(ptm.begin(), ptm.end(), EvaluatePreTokenizedEntry);
      //recalculate
      std::for_each(fragRefs.begin(), fragRefs.end(), std::mem_fun_ref(&FragValue::CalcWeight));
      //analyze
      if (!anlzer.RemoveBadFragment(fragRefs))
      {
        break;//finish
      }
      assert(!fragRefs.empty() || !"Invalid case");
    }
  }

  inline void ExtractTokens(const FragValsSet& fragRefs, TokensMap& tokens)
  {
    tokens.clear();
    for (FragValsSet::const_iterator it = fragRefs.begin(), lim = fragRefs.end(); it != lim; ++it)
    {
      tokens.insert(TokensMap::value_type(it->Value, StringFormatter::Process(TEXT_FORMAT_TOKEN_NAME, tokens.size())));
    }
  }

  inline EntriesMap::value_type Tok2Entry(const TokensMap::value_type& arg)
  {
    return EntriesMap::value_type(arg.second, Entry(Entry::LOCAL, Token::TEXT, arg.first));
  }

  class Pre2Entry : public std::unary_function<PreTokenizedMap::value_type, EntriesMap::value_type>
  {
  public:
    Pre2Entry(const TokensMap& tmap) : Tokens(tmap)
    {
    }

    result_type operator()(const argument_type& arg) const
    {
      result_type res(arg.first, Entry(Entry::GLOBAL));
      String::size_type tbeg(0);
      const String& text(arg.second.Value);
      for (FragmentsSet::const_iterator fit = arg.second.Fragments.begin(), flim = arg.second.Fragments.end();
           fit != flim; ++fit)
      {
        if (tbeg < fit->Begin)//text here
        {
          res.second.Value.push_back(Token(Token::TEXT, text.substr(tbeg, fit->Begin - tbeg)));
          tbeg = fit->Begin;
        }
        if (tbeg == fit->Begin)//variable here
        {
          TokensMap::const_iterator tit(Tokens.find(fit->FragHive->Value));
          assert(tit != Tokens.end());
          res.second.Value.push_back(Token(Token::VARIABLE, tit->second));
          tbeg += fit->Size;
        }
        else
        {
          assert(!"Overlapping regions detected");
        }
      }
      //remain text
      if (text.size() != tbeg)
      {
        res.second.Value.push_back(Token(Token::TEXT, text.substr(tbeg)));
      }
      return res;
    }
  private:
    const TokensMap& Tokens;
  };

  inline std::size_t CalcTokensSymbols(std::size_t base, const FragValsSet::value_type& val)
  {
    return base + val.Value.size();
  }

  inline std::size_t CalcTokensRefs(std::size_t base, const FragValsSet::value_type& val)
  {
    return base + val.RefCount();
  }

  inline std::size_t CalcTokenizedSymbols(std::size_t base, const FragValsSet::value_type& val)
  {
    return base + val.Value.size() * val.RefCount();
  }
  
  inline std::size_t CalcMaxToken(std::size_t base, const TokensMap::value_type& val)
  {
    return std::max(base, val.first.size());
  }
}

namespace Analyzer
{
  void ByFragments(const StringMap& source, const ByFragmentsParameters& params, EntriesMap& result, Statistic::Tokenizing& statistic)
  {
    statistic = Statistic::Tokenizing();
    PreTokenizedMap preMap;
    FragValsSet fragRefs;
    ExtractFragments(source, params, preMap, fragRefs);
    OptimizeFragments(params, preMap, fragRefs);
    TokensMap tokens;
    Log::Message(TEXT_MESSAGE_EXTRACTING_RESULT);
    ExtractTokens(fragRefs, tokens);
    //process locals
    std::transform(tokens.begin(), tokens.end(), std::inserter(result, result.end()), Tok2Entry);
    //process globals
    std::transform(preMap.begin(), preMap.end(), std::inserter(result, result.end()), Pre2Entry(tokens));
    //statistic
    statistic.TokensCount = tokens.size();
    statistic.TokensSymbols = std::accumulate(fragRefs.begin(), fragRefs.end(), 0, CalcTokensSymbols);
    statistic.TokensReferences = std::accumulate(fragRefs.begin(), fragRefs.end(), 0, CalcTokensRefs);
    statistic.TokenizedSymbols = std::accumulate(fragRefs.begin(), fragRefs.end(), 0, CalcTokenizedSymbols);
    statistic.MaxTokenSize = std::accumulate(tokens.begin(), tokens.end(), 0, CalcMaxToken);
  }
}
